package link_list;

import java.util.Iterator;

/**
 * @author swing
 * @description
 * @create 2022 - 11 - 18 0:24
 */
public class LinkedList_singe<E> implements Iterable<E> {

    private Node head;
    private int N;

    private class Node {
        E item;
        Node next;

        public Node(E item, Node next) {
            this.item = item;
            this.next = next;
        }

    }

    public LinkedList_singe() {
        this.head = new Node(null, null);
        this.N = 0;
    }

    /**
     * 清空单项链表
     * 1.将链表的头节点不指向下个节点
     * 2.将链表的长度设为0
     */
    public void clear() {
        head.next = null;
        N = 0;
    }

    /**
     * 判断链表的长度是否为空
     * 1头节点是否指向下个节点
     * 2长度是否为空
     *
     * @return
     */
    public boolean isEmpty() {

//        return head.next == null ? true : false;
        return N == 0;
    }

    public int length() {
        return N;
    }

    /**
     * 根据索引寻找元素
     * 遍历链表？
     * 从第一个节点开始找  一直遍历到第i个位置
     *
     * @param i
     * @return
     */
    public E get(int i) {
        Node node = head.next;
        for (int index = 0; index < i; index++) {
            node = node.next;
        }
        return node.item;
    }

    /**
     * 找到最后一个节点
     * 创建一个新节点保存需要存储的元素，将当前节点指向最后一个节点
     *
     * @param e
     */
    public void insert(E e) {
//        1.找到最后一个节点
        Node node = head;
        while (node.next != null) {
            node = node.next;
        }
        Node newNode = new Node(e, null);
        node.next = newNode;
        N++;
    }

    /**
     * 在第i个节点添加一个节点e
     * 1.找到第i个节点的上个节点的位置
     * 2.将上街节点指向这个需要添加的node ，然后之歌node指向上个节点的下个节点
     *
     * @param i
     * @param e
     */
    public void insert(int i, E e) {
      /* 不能这么写  如果i等于0呢？  也就是头节点的位置
       Node node = head.next;
        for (int index = 0; index < i; index++) {
            node = node.next;
        }
        Node iNode = new Node(e, node.next.next);
        node.next=iNode;
*/
        Node prev = head;
        for (int index = 0; index <= i - 1; index++) {
            prev = prev.next;
        }
        Node curr = prev.next;
        Node newNode = new Node(e, curr);
        prev.next = newNode;
        N++;

    }

    /**
     * :删除并返回线性表中第i个数据元素。
     * 找到第i个节点的上上个节点，指向第i+1个节点的元素
     *
     * @param i
     * @return
     */
    public E remove(int i) {
        Node prev = head;
        for (int index = 0; index <= i - 1; index++) {
            prev = prev.next;
        }
        Node curr = prev.next;
//        Node newNode = new Node(, curr);
        prev.next = curr.next;
        N--;
        return curr.item;
    }

    /**
     * :查找元素t在链表中第一次出现的位置
     *
     * @param e
     * @return
     */
    public int indexOf(E e) {
        Node node = head;
        for (int index = 0; node != null; index++) {
            node = node.next;
            if (node.item.equals(e)) {
                return index;
            }
        }
        return -1;
    }

    /**
     * 反转整个单向链表
     */
    public void reverse() {
        //当前链表为空不反转
        if (N == 0) {
            return;
        }
        reverse(head.next);
    }

    /**
     * @param curr 当前遍历的结点
     * @return 反转后当前结点上一个结点
     */
    public Node reverse(Node curr) {
//已经到了最后一个元素
        if (curr.next==null) {
            head.next=curr;
            return curr;
        }
        //当前节点的上个节点
        Node pre = reverse(curr.next);
        pre.next=curr; //
        curr.next=null;

        return curr;
    }

    /**
     * 提供更好的遍历体验
     *
     * @return
     */
    @Override
    public Iterator<E> iterator() {
        return new LIterator();
    }

    private class LIterator implements Iterator {
        private Node n;

        public LIterator() {
            this.n = head;
        }

        @Override
        public boolean hasNext() {
            return n.next != null;
        }

        @Override
        public Object next() {
            n = n.next;
            return n.item;
        }
    }
}









































